package com.Offer;

import com.pojo.TreeNode;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Arrays;

/*
    面试题7：重建二叉树
    题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假 设输入的前序遍历和中序遍历的结果中都不含重复的数字。
    例如输入前序遍历序列 {1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
    测试用例:前序遍历序列 {1,2,4,7,3,5,6,8}，中序遍历序列{4,7,2,1,5,3,8,6}
 */
public class demo7 {

    static int[] pre = new int[]{1,2,4,7,3,5,6,8};
    static int[] in = new int[]{4,7,2,1,5,3,8,6};
    public static void main(String[] args) {
        TreeNode rebuild = reConstructBinaryTree(pre,in);
        ArrayList<Integer> list = TreeNode.postorderTraverse(rebuild);
        for(int a:list){
            System.out.print(a+" ");
        }
    }

    //解法一：递归（传入数组的拷贝）
    public static TreeNode reConstructBinaryTree(int[] pre, int[] in){
        if(pre == null || in== null || pre.length == 0 || in.length == 0){
            return null;
        }
        if(pre.length != in.length){
            return null;
        }

        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0;i<pre.length;i++){
            if(pre[0] == in[i]){
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre,1,i+1),Arrays.copyOfRange(in,0,i));
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre,i+1,pre.length),Arrays.copyOfRange(in,i+1,in.length));
            }
        }
        return root;
    }

    //解放二：递归（传入子数组的边界索引）
    public static TreeNode reConstructBinaryTree2(int[] pre,int[] in){
        if(pre == null || in == null || pre.length == 0 || in.length == 0){
            return null;
        }
        return helper(pre,0,pre.length-1,in,0,in.length-1);
    }

    public static TreeNode helper(int[] pre,int preL,int preR,int[] in,int inL,int inR){
        if(preL > preR || inL > inR){
            return null;
        }
        int rootVal = pre[preL];
        int index = 0;
        while(index <= inR && in[index] != rootVal){
            index++;
        }
        TreeNode root = new TreeNode(rootVal);
        root.left = helper(pre,preL+1,preL-inL+index,in,inL,inR);
        root.right = helper(pre,preL-inL+index+1,preR,in,index+1,inR);
        return root;
    }
}
